The channel used in telecommunications systems often causes interference to data transmission. Interference occurs in all kinds of systems, but especially in wireless telecommunications systems, the transmission path attenuates and distorts in many different ways the signal being transmitted. The multipath propagation of the signal, different fades and reflections, and other signals being transmitted on the same transmission path typically cause interference on the transmission path.
To reduce the impact of the interference, several coding methods have been developed to protect signals from interference and to endeavour to eliminate errors caused by interference in signals. Convolutional coding is a much-used coding method. In convolutional coding, the signal to be transmitted that is made up of symbols is coded into code words that are based on the convolution of the symbols to be transmitted with so-called generator polynomials (coding polynomials). The coding ratio and coding polynomials define the convolutional code. The coding ratio (k/n) refers to the number (n) of the produced coded symbols in relation to the number (k) of the symbols to be coded. The coder is often a shift register. The constraint length (K) of a code often refers to the length of the shift register. The coder can be considered a state machine having 2K-1 states.
A receiver decodes the coded signal that propagated through the channel. A convolutional code is usually decoded using a trellis whose nodes describe the states of the encoder used in coding the signal, and the paths between the nodes belonging to different stages of the trellis describe the allowed state transitions. A decoder tries to find out the consecutive states of the coder, i.e. the transitions from one state to another. To find out the transitions, the decoder calculates metrics, of which there are two types: path metrics (or state metrics) and branch metrics. Path metrics represent the probability of the set of symbols in the received signal leading to the state described by the node in question. Branch metrics represent the probabilities of different transitions.
The basic element in calculating a trellis is a unit known as the ACS (Add, Compare, Select) unit, by means of which path metrics are calculated in the nodes by using the path metrics of the previous nodes and branch metrics between the nodes. To improve the efficiency of the equipment, two ACS units are often combined as a twin unit, also called a butterfly. Each unit can thus calculate two nodes simultaneously.
A convolutional code is usually decoded by means of the Viterbi algorithm. The Viterbi algorithm is a computationally demanding task. A general problem with the Viterbi algorithm is that when the constraint length of the convolutional code is long (e.g. 9, as in WCDMA of the UMTS system), the Viterbi algorithm must search through 2(9-1), i.e. 256, states to decode one bit. To achieve sufficient speed for such calculation, the calculation of several ACS units must be performed in parallel. A set of parallel twin ACS units is generally called a bank. There are typically fewer parallel ACS units than states in a trellis. This is why the calculated metrics must be stored in a cache memory. In implementations according to the prior art, there is one memory read-write operation per each new calculated metric. Therefore, the memory size is large and the data buses over which information is transmitted between the memories and ACS units are large. This in turn decreases the integration density when performing the calculation by hardware. For instance, if the implementation comprises 32 parallel ACS units and the path metric is presented as 12-bit figures, the memory and data bus is 384 bits wide.
When the calculation is done by software, the performance of the decoder software is decreased by high memory usage that is substantially slower than the use of processor registers. The number of registers in a processor is limited.